home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 November: Tool Chest / Dev.CD Nov 94.toast / Tool Chest / Networking / Network Watch (DMZ) v1.3 / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-06-16  |  1.7 KB  |  110 lines  |  [TEXT/MPS ]
  1.  
  2. /*
  3.  *  qsort.c
  4.  *
  5.  *  Copyright (c) 1991 Symantec Corporation.  All rights reserved.
  6.  *
  7.  */
  8.  
  9. #include "stdlib.h"
  10.  
  11. static char *qBase;
  12. static size_t qSize;
  13. static __cmp_func qCompare;
  14.  
  15. static int std_compare(size_t, size_t);
  16. static void std_swap(size_t, size_t);
  17.  
  18. static void qsort1(size_t, size_t);
  19. static __cmp1_func q1Compare;
  20. static __swap1_func q1Swap;
  21.  
  22.  
  23. /* ---------- standard quicksort ---------- */
  24.  
  25.  
  26. void
  27. qsort(void *base, size_t n, size_t size, __cmp_func compare)
  28. {
  29.     qBase = base;
  30.     qSize = size;
  31.     qCompare = compare;
  32.     _qsort(n, std_compare, std_swap);
  33. }
  34.  
  35.  
  36. static int
  37. std_compare(size_t i, size_t j)
  38. {
  39.     return((*qCompare)(qBase + i * qSize, qBase + j * qSize));
  40. }
  41.  
  42.  
  43. static void
  44. std_swap(size_t i, size_t j)
  45. {
  46.     register size_t size = qSize;
  47.     register void *p = qBase + i * size;
  48.     register void *q = qBase + j * size;
  49.     
  50.     asm {
  51. @1        move.b    (p),d0
  52.         move.b    (q),(p)+
  53.         move.b    d0,(q)+
  54.         subq.l    #1,size
  55.         bne.s    @1
  56.     }
  57. }
  58.  
  59.  
  60. /* ---------- general quicksort ---------- */
  61.  
  62.  
  63. void
  64. _qsort(size_t n, __cmp1_func compare, __swap1_func swap)
  65. {
  66.     q1Compare = compare;
  67.     q1Swap = swap;
  68.     qsort1(0, n);
  69. }
  70.  
  71.  
  72. /*
  73.  *  sort elements "first" through "last"-1
  74.  *
  75.  */
  76.  
  77. static void
  78. qsort1(size_t first, size_t last)
  79. {
  80.     static size_t i;        /*  "static" to save stack space  */
  81.     size_t j;
  82.  
  83.     while (last - first > 1) {
  84.         i = first;
  85.         j = last;
  86.         for (;;) {
  87.             while (++i < last && (*q1Compare)(i, first) < 0)
  88.                 ;
  89.             while (--j > first && (*q1Compare)(j, first) > 0)
  90.                 ;
  91.             if (i >= j)
  92.                  break;
  93.             (*q1Swap)(i, j);
  94.         }
  95.         if (j == first) {
  96.             ++first;
  97.             continue;
  98.         }
  99.         (*q1Swap)(first, j);
  100.         if (j - first < last - (j + 1)) {
  101.             qsort1(first, j);
  102.             first = j + 1;    /*  qsort1(j + 1, last);  */
  103.         }
  104.         else {
  105.             qsort1(j + 1, last);
  106.             last = j;        /*  qsort1(first, j);  */
  107.         }
  108.     }
  109. }
  110.